home *** CD-ROM | disk | FTP | other *** search
/ Sprite 1984 - 1993 / Sprite 1984 - 1993.iso / src / kernel / sched / schedQueue.c < prev    next >
Encoding:
C/C++ Source or Header  |  1992-12-19  |  9.2 KB  |  312 lines
  1. /* 
  2.  * schedQueue.c --
  3.  *
  4.  *    Routines for ordering processes in the run queue based on weighted
  5.  *    usage.
  6.  *
  7.  * Copyright 1985 Regents of the University of California
  8.  * All rights reserved.
  9.  */
  10.  
  11. #ifndef lint
  12. static char rcsid[] = "$Header: /cdrom/src/kernel/Cvsroot/kernel/sched/schedQueue.c,v 9.3 90/10/05 17:14:29 mendel Exp $ SPRITE (Berkeley)";
  13. #endif /* not lint */
  14.  
  15.  
  16. #include <sprite.h>
  17. #include <mach.h>
  18. #include <proc.h>
  19. #include <list.h>
  20. #include <sync.h>
  21. #include <sched.h>
  22. #include <schedInt.h>
  23.  
  24. List_Links schedReadyQueueHeader;
  25. List_Links *schedReadyQueueHdrPtr = &schedReadyQueueHeader;
  26.  
  27.  
  28. Sched_OnDeck    sched_OnDeck[MACH_MAX_NUM_PROCESSORS];
  29.  
  30. int    sched_Insert;
  31. int    sched_QueueEmpty;
  32. int    sched_Stage;
  33. int    sched_Preempt;
  34.  
  35.  
  36. /*
  37.  * ----------------------------------------------------------------------------
  38.  *
  39.  * Sched_SetClearUsageFlag --
  40.  *
  41.  *    Set flag in process table entry for the current process that says to
  42.  *    clear usage info whenever is scheduled.
  43.  *
  44.  * Results:
  45.  *    None.
  46.  *
  47.  * Side effects:
  48.  *    schedFlags field modified for calling process.
  49.  *
  50.  * ----------------------------------------------------------------------------
  51.  */
  52. void
  53. Sched_SetClearUsageFlag()
  54. {
  55.     Proc_ControlBlock    *procPtr;
  56.  
  57.     procPtr = Proc_GetCurrentProc();
  58.     MASTER_LOCK(sched_MutexPtr);
  59.     procPtr->schedFlags |= SCHED_CLEAR_USAGE;
  60.     MASTER_UNLOCK(sched_MutexPtr);
  61. }
  62.  
  63. /*
  64.  * ----------------------------------------------------------------------------
  65.  *
  66.  * Sched_InsertInQueue --
  67.  *
  68.  *    Given a pointer to a process, move it in the run queue (or insert
  69.  *    it if it is not already there) based on its current weighted usage.
  70.  *    If the process is of higher priority than the current process,
  71.  *    flag the current process as having a pending context switch.
  72.  *
  73.  * Results:
  74.  *    None.
  75.  *
  76.  * Side effects:
  77.  *    Process is moved within or added to the run queue.  If the process
  78.  *    is added, the global count of the number of ready processes is
  79.  *    incremented.
  80.  *
  81.  * ----------------------------------------------------------------------------
  82.  */
  83.  
  84. INTERNAL void
  85. Sched_InsertInQueue(procPtr, runPtrPtr)
  86.     register Proc_ControlBlock    *procPtr;    /* pointer to process to 
  87.                            move/insert */
  88.     Proc_ControlBlock        **runPtrPtr;    /* returns process from 
  89.                          * front of queue.
  90.                          */
  91. {
  92.     register Proc_ControlBlock     *itemProcPtr;
  93.     register List_Links        *queuePtr;
  94.     Boolean            insert;
  95.     Boolean            delete;
  96.     Boolean            foundInsertPoint;
  97.     List_Links            *followingItemPtr;
  98.     int                i;
  99.     Proc_ControlBlock        *lowestProcPtr;
  100.     int                processor;
  101.  
  102.     sched_Insert++;
  103.     if (procPtr->schedFlags & SCHED_CLEAR_USAGE) {
  104.     procPtr->recentUsage = 0;
  105.     procPtr->weightedUsage = 0;
  106.     procPtr->unweightedUsage = 0;
  107.     }
  108.     processor = procPtr->processor;
  109.     queuePtr = schedReadyQueueHdrPtr;
  110.     if (mach_NumProcessors > 1) {
  111.     if (sched_ProcessorStatus[processor] == 
  112.         SCHED_PROCESSOR_COUNTING_TICKS) {
  113.         if (sched_OnDeck[processor].procPtr != (Proc_ControlBlock *) NIL) {
  114.         panic("Count of ticks screwed up.");
  115.         }
  116.         sched_OnDeck[processor].procPtr = procPtr;
  117.         if (runPtrPtr != (Proc_ControlBlock **) NIL) {
  118.         *runPtrPtr = (Proc_ControlBlock *) NIL;
  119.         }
  120.         return;
  121.     } else if (List_IsEmpty(queuePtr)) {
  122.         /*
  123.          * Special case an empty queue. If the queue is empty there may be
  124.          * idle processors. We optimize things by bypassing the queue and
  125.          * giving processes to the processors through the staging areas.
  126.          */
  127.  
  128.         sched_QueueEmpty++;
  129.         /*
  130.          * If we are supposed to return a runnable process and the process
  131.          * we were given last ran on the current processor, then just return
  132.          * the process.
  133.          */
  134.         if ((runPtrPtr != (Proc_ControlBlock **) NIL) && 
  135.         (processor == Mach_GetProcessorNumber())) {
  136.         *runPtrPtr = procPtr;
  137.         return;
  138.         }
  139.         /*
  140.          * If the last processor to run the process is idle then just give
  141.          * the process to that processor.
  142.          */
  143.         if ((proc_RunningProcesses[processor] == (Proc_ControlBlock *) NIL) &&
  144.         (sched_ProcessorStatus[processor] == SCHED_PROCESSOR_ACTIVE)) {
  145.         if (sched_OnDeck[processor].procPtr == 
  146.             (Proc_ControlBlock *) NIL) {
  147.             sched_OnDeck[processor].procPtr = procPtr;
  148.             procPtr =  (Proc_ControlBlock *) NIL;
  149.         /*
  150.          * There is already a process on deck, but the one new one
  151.          * can't be run by anyone else because it's stack is in
  152.          * use by this processor. Switch the two processes.
  153.          */
  154.         } else if (procPtr->schedFlags & SCHED_STACK_IN_USE) {
  155.             Proc_ControlBlock *tempPtr;
  156.     
  157.             tempPtr = procPtr;
  158.             procPtr = sched_OnDeck[processor].procPtr;
  159.             sched_OnDeck[processor].procPtr = tempPtr;
  160.         }
  161.         }
  162.         if (procPtr != (Proc_ControlBlock *) NIL && 
  163.         !(procPtr->schedFlags & SCHED_STACK_IN_USE)) {
  164.         /*
  165.          * Give the process to any idle processor. It's stack cannot
  166.          * be in use (it can't be run anyway so don't bother trying).
  167.          */
  168.         for (i = 0; i < mach_NumProcessors; i++) {
  169.             if ((sched_ProcessorStatus[i] == SCHED_PROCESSOR_ACTIVE) &&
  170.             (proc_RunningProcesses[i] ==  (Proc_ControlBlock *) NIL) &&
  171.             (sched_OnDeck[i].procPtr == 
  172.             (Proc_ControlBlock *) NIL)) {
  173.             sched_OnDeck[i].procPtr = procPtr;
  174.             procPtr =  (Proc_ControlBlock *) NIL;
  175.             break;
  176.             }
  177.         }
  178.         }
  179.         /* 
  180.          * If we gave the process away then we're done.
  181.          */
  182.         if (procPtr == (Proc_ControlBlock *) NIL) {
  183.         sched_Stage++;
  184.         if (runPtrPtr != (Proc_ControlBlock **) NIL) {
  185.             *runPtrPtr = (Proc_ControlBlock *) NIL;
  186.         }
  187.         return;
  188.         }
  189.     }
  190.     }
  191.     /*
  192.      * Compare the process's weighted usage to the usage of the currently
  193.      * running processes.  If the new process has higher priority (lower
  194.      * usage) than one of the current processes, then force the current 
  195.      * process to context switch.  
  196.      * The context switch will occur in one of two places. 
  197.      * 1) If we are being called at interrupt level, and the interrupt occurred
  198.      *    in user mode, then the context switch will occur prior to returning 
  199.      *      to user mode. (the CallInterruptHandler macro checks the 
  200.      *    specialHandling flag)
  201.      * 2) The next time the current process enters a trap handler.
  202.      *
  203.      */
  204.     lowestProcPtr = (Proc_ControlBlock *) NIL;
  205.     for (i = 0; i < mach_NumProcessors; i++) {
  206.     itemProcPtr = proc_RunningProcesses[i];
  207.     if (itemProcPtr == (Proc_ControlBlock *) NIL) {
  208.         continue;
  209.     }
  210.     if ((lowestProcPtr == (Proc_ControlBlock *) NIL) ||
  211.         (itemProcPtr->weightedUsage > lowestProcPtr->weightedUsage)) {
  212.         lowestProcPtr = itemProcPtr;
  213.     }
  214.     }
  215.     if ((lowestProcPtr != (Proc_ControlBlock *) NIL) &&
  216.         (procPtr->weightedUsage < lowestProcPtr->weightedUsage)) {
  217.     sched_Preempt++;
  218.     lowestProcPtr->schedFlags |= SCHED_CONTEXT_SWITCH_PENDING;
  219.     lowestProcPtr->specialHandling = 1;
  220.     }
  221.     if (List_IsEmpty(queuePtr)) {
  222.     /*
  223.      * This is easy if the queue is empty.
  224.      */
  225.     if (runPtrPtr != (Proc_ControlBlock **) NIL) {
  226.         *runPtrPtr = procPtr;
  227.         return;
  228.     } else {
  229.         List_Insert((List_Links *) procPtr, LIST_ATREAR(queuePtr));
  230.         sched_Instrument.numReadyProcesses = 1;
  231.         return;
  232.     }
  233.     }
  234.     /*
  235.      * Loop through all elements in the run queue.  Search for the first
  236.      * process with a weighted usage greater than the process being inserted.
  237.      *
  238.      * If a process is found that belongs after procPtr, set foundInsertPoint
  239.      * and just look for procPtr to see whether the process is being moved
  240.      * or inserted.  If procPtr has already been found and the insert point
  241.      * has been determined, exit the loop.
  242.      */
  243.     insert = TRUE;
  244.     delete = FALSE;
  245.     foundInsertPoint = FALSE;
  246.     itemProcPtr = (Proc_ControlBlock *) schedReadyQueueHdrPtr;
  247.     followingItemPtr = (List_Links *) NIL;
  248.     LIST_FORALL(queuePtr, (List_Links *) itemProcPtr) {
  249.     if (itemProcPtr == procPtr) {
  250.         delete = TRUE;
  251.     }
  252.     if (foundInsertPoint && delete) {
  253.         break;
  254.     }
  255.     if (foundInsertPoint) {
  256.         continue;
  257.     }
  258.     if (procPtr->weightedUsage < itemProcPtr->weightedUsage) {
  259.         followingItemPtr = (List_Links *) itemProcPtr;
  260.         if (((List_Links *)(procPtr))->nextPtr == 
  261.         (List_Links *) followingItemPtr && delete) {
  262.         insert = FALSE;
  263.         delete = FALSE;
  264.         break;
  265.         }
  266.         foundInsertPoint = TRUE;
  267.     }
  268.     }
  269.     if (foundInsertPoint) {
  270.     itemProcPtr = (Proc_ControlBlock *)LIST_BEFORE(followingItemPtr);
  271.     }
  272.     /*
  273.      * Process was already on queue in a different position so delete it.
  274.      */
  275.     if (delete) {
  276.     List_Remove((List_Links *) procPtr);
  277.     sched_Instrument.numReadyProcesses -= 1;
  278.     }
  279.     if (runPtrPtr != (Proc_ControlBlock **) NIL) {
  280.     if (foundInsertPoint && (List_Links *)itemProcPtr == queuePtr) {
  281.         /*
  282.          * We are being inserted at the front
  283.          * of the queue so return ourselves.
  284.          */
  285.         *runPtrPtr = procPtr;
  286.         return;
  287.     }
  288.     }
  289.     /*
  290.      * Insert the process into the queue.
  291.      */
  292.     if (insert) {
  293.     if (foundInsertPoint) {
  294.         List_Insert((List_Links *) procPtr, (List_Links *) itemProcPtr);
  295.     } else {
  296.         List_Insert((List_Links *) procPtr, LIST_ATREAR(queuePtr));
  297.     }
  298.     sched_Instrument.numReadyProcesses += 1;
  299.     }
  300.     /*
  301.      * If we are to return a process then delete the first process from
  302.      * the queue.
  303.      */
  304.     if (runPtrPtr != (Proc_ControlBlock **) NIL) {
  305.     Proc_ControlBlock     *tempPtr;
  306.     tempPtr = (Proc_ControlBlock *)List_First(queuePtr);
  307.     List_Remove((List_Links *)tempPtr);
  308.     *runPtrPtr = tempPtr;
  309.     sched_Instrument.numReadyProcesses -= 1;
  310.     }
  311. }
  312.